package com.algrithom.graph.shortestpath;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

import com.common.model.Vertex;
import com.google.common.base.Preconditions;

/**
 * 解决负权边，解决单源最短路径
 * 有向图+有负权边/无负权边+无负权环
 *
 * @author think
 * @version 1.0.0
 * @since 2020/2/12
 */
public class BellManFold {
    
    public static void main(String[] args){
        List<Vertex> vertices = new ArrayList<>();
        Vertex preVertex = Vertex.builder().number(0).build();
        Vertex nextVertex = Vertex.builder().number(1).weight(10).build();
        preVertex.setNextNode(nextVertex);
        nextVertex = Vertex.builder().number(3).weight(8).build();
        preVertex.getNextNode().setNextNode(nextVertex);
        vertices.add(preVertex);
        
        preVertex = Vertex.builder().number(1).build();
        nextVertex = Vertex.builder().number(5).weight(2).build();
        preVertex.setNextNode(nextVertex);
        vertices.add(preVertex);
        
        preVertex = Vertex.builder().number(2).build();
        nextVertex = Vertex.builder().number(1).weight(1).build();
        preVertex.setNextNode(nextVertex);
        vertices.add(preVertex);
        
        preVertex = Vertex.builder().number(3).build();
        nextVertex = Vertex.builder().number(4).weight(1).build();
        preVertex.setNextNode(nextVertex);
        vertices.add(preVertex);
        
        preVertex = Vertex.builder().number(4).build();
        nextVertex = Vertex.builder().number(5).weight(-1).build();
        preVertex.setNextNode(nextVertex);
        nextVertex = Vertex.builder().number(1).weight(-4).build();
        preVertex.getNextNode().setNextNode(nextVertex);
        vertices.add(preVertex);
        
        preVertex = Vertex.builder().number(5).build();
        nextVertex = Vertex.builder().number(2).weight(-2).build();
        preVertex.setNextNode(nextVertex);
        vertices.add(preVertex);
        
        bellManFoldAlg(0,vertices);
    }
    
    public static void bellManFoldAlg(int source,List<Vertex> vertices){
        int size = vertices.size();
        Preconditions.checkArgument(source < size);
        
        int[] dis = new int[size];
        boolean[] flag = new boolean[size];
        init(size,dis,flag);
        
        dis[source] = 0;
        flag[source] = true;
        Deque<Integer> queue = new LinkedList<>();
        queue.offer(source);
        while (!queue.isEmpty()) {
            int uIndex = queue.poll();
            flag[uIndex] = false;
            Vertex nextNode = vertices.get(uIndex).getNextNode();
            while (nextNode != null) {
                if (nextNode.getWeight() < Integer.MAX_VALUE && dis[uIndex] + nextNode.getWeight() < dis[nextNode.getNumber()]) {
                    dis[nextNode.getNumber()] = dis[uIndex] + nextNode.getWeight();
                    if (!flag[nextNode.getNumber()]) {
                        queue.offer(nextNode.getNumber());
                        flag[nextNode.getNumber()] = true;
                    }
                }
                nextNode = nextNode.getNextNode();
            }
        }
        for (int i = 0; i < size; i++) {
            System.out.println(source + "->" + vertices.get(i).getNumber() + ":" + dis[i]);
        }
    }
    
    private static void init(int size,int[] dis,boolean[] flag){
        for (int i = 0; i < size; i++) {
            dis[i] = Integer.MAX_VALUE;
            flag[i] = false;
        }
    }
}
